// https://leetcode.cn/problems/n-queens/

/*
思路：回溯

*/

#include <iostream>
#include <string>
#include <vector>


using namespace std;

class Solution {
public:
	vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
		vector<string> matrix(n, string(n, '.'));
		insertQueues(matrix, 0, n);
		return res;
    }
	
	void insertQueues(vector<string> & matrix, int row, int & len){
		if(row == len){
			res.push_back(matrix);
			return;
		}
		for(int i = 0; i < len; i++){
			if(isSafe(matrix, len, row, i)){
				matrix[row][i] = 'Q';
				insertQueues(matrix, row + 1, len);
				matrix[row][i] = '.';
			}
		}
	}
	
	// 判定当前matrix是否是有效的
	// row - 行  column - 列
 	bool isSafe(vector<string> & matrix, int & len, int & row, int & column){
		for(int i = 0; i < len; i++){
			if(i != row && matrix[i][column] == 'Q') return false;
			if(i != column && matrix[row][i] == 'Q') return false;
			// 45度
			if(i != 0 && (row + i) < len && (column - i) >= 0 && matrix[row + i][column - i] == 'Q') return false;
			if(i != 0 && (row - i) >= 0 && (column + i) < len && matrix[row - i][column + i] == 'Q') return false;

			// 135度
			if(i != 0 && (row - i) >= 0 && (column - i) >= 0 && matrix[row - i][column - i] == 'Q') return false;
			if(i != 0 && (row + i) < len && (column + i) < len && matrix[row + i][column + i] == 'Q') return false;
		}
		return true;
	}
};

int main(){
	Solution so;
	auto res = so.solveNQueens(4);
	for(auto items : res){
		for(auto item : items){
			cout << item << endl;
			
		}
		cout << endl;
	}
	return 0;
}